#include <cstdlib>
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <stack>
												
static const int N=1000;
using namespace std;

int appartient(int a,int i,vector<int> voisins[]){

		for(int j=0; j<voisins[a].size(); j++){

			if(voisins[a][j]==i)
				return 1;

		}

	return 0;



}

void voisinstrandom(int n, int m, vector<int> voisins[]){
	int arr=0;
	srand(time(NULL));
	int i;
	int tmp;
	while(arr<m){
		tmp=rand()%n;
		i=rand()%n;
		while(tmp==i || appartient(tmp, i, voisins )) {
			tmp=rand()%n;
		}

		voisins[i].push_back(tmp);
		voisins[tmp].push_back(i);
		arr++;
		i++;
		tmp=-1;
	}
}


void parcourslargeur(int n, vector<int> voisins[], int niveau[], int ordre[], int pere[]){
	
	int dv[N];
	queue<int> at;
	int tmp;
	int x;
	
	for(int i(0); i<n ; i++){
		dv[i]=0;
	}
	

	dv[0]=1; ordre[0]=1; pere[0]=0; niveau[0]=0; at.push(0); int t=2;

	while(at.size()!=0){
	
		
		tmp=at.front();
		at.pop();
		for(int j(0); j<voisins[tmp].size(); j++){
			x=voisins[tmp][j];
		
			if(dv[x]==0){
				
				dv[x]=1;
				at.push(x);
				ordre[x]=t; t++;
				pere[x]=tmp;
				niveau[x]=niveau[tmp]+1;


			}


		 }
	

	}

}


void parcoursProf(int n, vector<int> voisins[], int pere[]){
	
	int dv[N];
	int debut[N];
	int fin[N];
	stack<int> at;
	int tmp;
	int x;
	int t;
	
	for(int i(0); i<n ; i++){
		dv[i]=0;
	}
	

	dv[0]=1; pere[0]=0; at.push(0); t=2;
	
	while(at.size()!=0){
	
		
		tmp=at.top();
		if(voisins[tmp].size()==0){
			at.pop();
			fin[tmp]=t; t++;
		}
		else{
			x=voisins[tmp][voisins[tmp].size()-1];
			voisins[tmp].pop_back();
		
			if(dv[x]==0){
			
				dv[x]=1;
				at.push(x);
				debut[x]=t; t++;
				pere[x]=tmp;
			}

				
			


		 }
	

	}

}








void affichage(int n, int niveau[]){

	int lvl[N];
	int tmp(0);
	int t(0);

	for(int j(0); j<N; j++){
		lvl[j]=-1;
	}
	
	for(int i(0); i<n; i++){

		if(niveau[i]!=-1){
			if(lvl[niveau[i]]==-1){
			lvl[niveau[i]]=1;
		
			}
			else{
			lvl[niveau[i]]++;
			}
		}
	}

	

	while(lvl[t]!=-1){

		if(lvl[t]!=0){
			cout<<"il y a "<<lvl[t]<<" sommets au niveau "<<t<<endl;
			tmp+=lvl[t];
		}
		t++;
	}

	cout<<"il y a "<<n-tmp<<" sommets qui ne sont pas dans la composante"<<endl;


	
	
}

int main(){
char tmp;
int n;             //Le nombre de sommets.
int m;             // Le nombre d'aretes.
cout << "Entrer le nombre de sommets: ";
cin >> n;
cout << "Entrer le nombre d'aretes: ";
cin >> m;
vector<int> voisins[N];	// Les listes des voisins. 
int pere[N];            // L'arbre en largeur.
int ordre[N];           // L'ordre de parcours.
int niveau[N];          // Le niveau du point.

	for(int i(0); i<N; i++){
		niveau[i]=-1;
	}


voisinstrandom(n, m, voisins);
cout<<"Voulez vous utiliser Parcours en profondeur ou en largeur?\n	Profondeur : p\n	Largeur : l"<<endl;
cin>>tmp;
switch(tmp){
	
	case 'l' :parcourslargeur(n, voisins, niveau, ordre, pere);
	break;
	
	case 'p' :parcoursProf(n, voisins, pere);
	break;
	
	default : cout<<"erreur de saisie"<<endl;
	break;
}

affichage(n, niveau);



return 0;

}



